import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description:数字字符串转化成IP地址
 * User: wangxin
 * Date: 2025-02-08
 * Time: 20:47
 */
public class Test2 {
    //方法一：枚举法
    public ArrayList<String> restoreIpAddresses1 (String s) {
        // write code here
        ArrayList<String> res = new ArrayList<>();
        int n = s.length();
        for(int i = 1;i < 4&&i < n-2;i++){
            for(int j = i+1;j < i+4&&j < n-1;j++){
                for(int k = j+1;k < j+4&&k < n;k++){
                    if(n-k >= 4){
                        continue;
                    }
                    String a = s.substring(0,i);
                    String b = s.substring(i,j);
                    String c = s.substring(j,k);
                    String d = s.substring(k);
                    if(Integer.parseInt(a) > 255||Integer.parseInt(b) > 255
                            ||Integer.parseInt(c) > 255||Integer.parseInt(d) > 255){
                        continue;
                    }
                    if((a.length()!= 1&&a.charAt(0) =='0')
                            ||(b.length()!= 1&&b.charAt(0) =='0')
                            ||(c.length()!= 1&&c.charAt(0) =='0')
                            ||(d.length()!= 1&&d.charAt(0) =='0')){
                        continue;
                    }
                    String t = a+'.'+ b +'.'+ c +'.'+ d;
                    res.add(t);
                }
            }
        }
        return res;
    }
    //==================================================================================
    //方法二：递归+回溯
    private String nums = "";
    public void dfs(String s,ArrayList<String> res,int step,int index){
        String cur = "";
        if(step == 4){
            if(index != s.length())
                return;
            res.add(nums);
        }else{
            for(int i = index; i < index+3&&i < s.length();i++){
                cur += s.charAt(i);
                int num = Integer.parseInt(cur);
                String temp = nums;
                if(num <= 255&&(cur.length()==1||cur.charAt(0)!='0')){
                    if(step -3 != 0){
                        nums += cur+".";
                    }else{
                        nums += cur;
                    }
                    dfs(s,res,step+1,i+1);
                    nums = temp;
                }
            }
        }

    }
    public ArrayList<String> restoreIpAddresses2 (String s) {
        // write code here
        ArrayList<String> res = new ArrayList<>();
        dfs(s,res,0,0);
        return res;
    }
}
